package leetcode105

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// 前序遍历 preorder = [3,9,20,15,7]
//中序遍历 inorder = [9,3,15,20,7]
func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 {
		return nil
	}
	nodeVal := preorder[0]
	root := &TreeNode{
		Val: nodeVal,
	}
	if len(preorder) == 1 {
		return root
	}
	var num int // 0,num左子树中序 1,num+1左子树前序
	for k, v := range inorder {
		if v == preorder[0] {
			num = k
			break //寻找到当前根节点在中序遍历中的位置
		}
	}
	root.Left = buildTree(preorder[1:num+1], inorder[:num]) //递归左子树
	root.Right = buildTree(preorder[num+1:], inorder[num+1:])

	return root
}
